package com.ting.test.algorithms.背包类问题;

/**
 * arr是货币数组，其中的值都是正数。再给定一个正数aim。
 * 每个值都认为是一张货币，
 * 返回组成aim的最少货币数
 * 注意：
 * 因为是求最少货币数，所以每一张货币认为是相同或者不同就不重要了
 */
public class 返回组成aim的最少货币数 {
    public static void main(String[] args) {
        int maxLen = 20;
        int maxValue = 30;
        int N = (int) (Math.random() * maxLen);
        int[] arr = randomArray(N, maxValue);
        int aim = (int) (Math.random() * maxValue);
        int count = mincoins(0, arr, aim);
        System.out.println(count);

    }

    private static int mincoins(int index, int[] arr, int rest) {
        //不存在这种情况
        if (rest < 0) {
            return Integer.MAX_VALUE;
        }

        //到头了
        if (index == arr.length) {
            return rest == 0 ? 0 : Integer.MAX_VALUE;
        }

        //对于当前硬币而言，有两种选择，1.不要，2要
        //p1表示 如果不要当前硬币，下一个硬币之后的所有硬币组成catacity面值时，使用的最少张数
        int p1 = mincoins(index + 1, arr, rest);
        // p2表示如果要当前硬币，则下一个硬币之后所有硬币组成catacity-arr[index]面值的使用的最小张数
        int p2 = mincoins(index + 1, arr, rest - arr[index]);
        if (p2 != Integer.MAX_VALUE) {
            p2++;
        }
        //取最小值
        return Math.min(p1, p2);
    }


    // 为了测试
    public static int[] randomArray(int N, int maxValue) {
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = (int) (Math.random() * maxValue) + 1;
        }
        return arr;
    }

    // 为了测试
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
